package pen_exam.xiaomi_2024_03_23;

import codingforgreat.class38.Class02_GreatWall;
import com.sun.deploy.panel.ITreeNode;

import java.util.Arrays;
import java.util.Scanner;


//5 4
//6 5 3 4 6
//1 3 2
//4 4 2
//3 5 1
//1 5 6
//预期结果：4 第四次操作后才有最小值为负数的山
/**
 * 第一行：长度 操作次数
 * 第二行 山数组
 * 往下m行： 下标从1开始 arr[0] - arr[1] 同时削去高度 arr[2]
 * */
public class Class02_MoveMountion {
    //线段树求min
    public static class SegmentTree{
        int MAXN;
        int[] arr;
        int[] min;
        int[] sub;
        public SegmentTree(int[] arr){
             MAXN = arr.length + 1;
             this.arr = new int[MAXN];
            for (int i = 1; i < MAXN; i++) {
                this.arr[i] = arr[i - 1];
            }
            min = new int[MAXN << 2];
            sub = new int[MAXN << 2];
            Arrays.fill(min,Integer.MAX_VALUE);
        }
        public void pushUp(int rt){
            min[rt] = Math.min(min[rt << 1], min[rt << 1 | 1]);
        }
        public void build(int l, int r, int rt){
            if (l == r) {
                min[rt] = Math.min(min[rt],arr[l]);
                return;
            }
            int mid = (l + r) >> 1;
            build(l, mid, rt << 1);
            build(mid + 1, r, rt << 1 | 1);
            pushUp(rt);
        }
        public void add(int L,int R,int C,int l,int r,int rt){
            //任务把格子全包 懒住
            if(L <= l && R >= r){
                sub[rt] += C;
                min[rt] -= C;
                return;
            }
            //任务没有把当前格子全包
            int mid = ( l + r ) >> 1;
            pushDown(rt);
            if(L <= mid){
                add(L, R, C, l, mid, rt << 1);
            }
            if(R > mid){
                add(L, R, C, mid + 1, r, rt << 1 | 1);
            }
            pushUp(rt);
        }
        public void pushDown(int rt){
            if(sub[rt] != 0){
                sub[rt << 1] += sub[rt];
                sub[rt << 1 | 1] += sub[rt];
                min[rt << 1] -= sub[rt];
                min[rt << 1 | 1] -= sub[rt];
                sub[rt] = 0;
            }
        }
        public int query(int L, int R, int l, int r, int rt) {
            if (L <= l && r <= R) {
                return min[rt];
            }
            int mid = (l + r) >> 1;
            pushDown(rt);
            int left = 0;
            int right = 0;
            if (L <= mid) {
                left = query(L, R, l, mid, rt << 1);
            }
            if (R > mid) {
                right += query(L, R, mid + 1, r, rt << 1 | 1);
            }
            return Math.min(left,right);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        str = sc.nextLine().split(" ");
        int[] mountions = new int[n];
        for (int i = 0; i < n; i++) {
            mountions[i] = Integer.parseInt(str[i]);
        }
        int[][] move = new int[m][3];
        for (int i = 0; i < m; i++) {
            String[] mov = sc.nextLine().split(" ");
            move[i][0] = Integer.parseInt(mov[0]);
            move[i][1] = Integer.parseInt(mov[1]);
            move[i][2] = Integer.parseInt(mov[2]);
        }
        sc.close();
        SegmentTree seg = new SegmentTree(mountions);
        seg.build(1,n,1);
        for (int i = 0; i < m; i++) {
            seg.add(move[i][0],move[i][1],move[i][2],1,n,1);
           int min = seg.query(move[i][0],move[i][1],1,n,1);
           if(min < 0){
               System.out.println(i + 1);
               break;
           }
        }
    }
}
